import java.util.ArrayList;
import java.util.PriorityQueue;


public class PLUtil {

static int[] toIntArray(ArrayList<Integer> list)  {
    int[] ret = new int[list.size()];
    int i = 0;
    for (Integer e : list)  
        ret[i++] = e.intValue();
    return ret;
}

	
static int find_first_greater_than(float[] data, float key, int begin, int end) {
	int index = -1;
	if (data == null || data.length == 0 || begin < 0 || end < begin || end > data.length)
		return index;
 
	int posStart = begin;
	int posEnd = end;
	int mid = 0;
	while (posStart <= posEnd) {
		mid = (posStart + posEnd) / 2;
		if (data[mid] < key) {
			posStart = mid + 1;
		} else {
		// we found a value that is greater, this may be the index
			index = mid;
			posEnd = mid - 1;
		}
	}
	return index;
}

static int find_first_greater_than(float [ ] data, float key) {
	if (data == null || data.length == 0)
		return -1;
	
	return find_first_greater_than(data, key, 0, data.length);
}

static int[] k_dominant_indices(float[ ] data, int k) {
	if (data == null || data.length == 0)
		return null;


	//if the data length is smaller than k, return all indices
	if (data.length <= k) {
		int[] indices = new int[data.length];
		for (int i = 0; i < data.length; ++i) {
			indices[i] = i;
		}
		return indices;
	}

	int[] indices = new int[k];

	PriorityQueue<PQNodeDes> queue = new PriorityQueue<PQNodeDes>(data.length);

	for (int i=0; i< data.length; ++i) {
		queue.add(new PQNodeDes(i, data[i]));
	}
	
	// get the first k nodes
	for (int i = 0;i< k; ++i) {
		PQNodeDes node = queue.poll();
		indices[i] = node.GetIndex();
	}
	
	return indices;
}


static int[] dominant_indices_wieght_sum(float[] data, float totalWeight) {
	if (data == null || data.length == 0)
		return null;


	ArrayList<Integer> indices = new ArrayList<Integer> ();

	PriorityQueue<PQNodeDes> queue = new PriorityQueue<PQNodeDes>(data.length);

	for (int i=0; i< data.length; ++i) {
		queue.add(new PQNodeDes(i, data[i]));
	}
	
	float weight = 0;	
	// get the first k nodes

	int i =0;
	while(weight < totalWeight && i < queue.size()) {
		PQNodeDes node = queue.poll();
		indices.add(node.GetIndex());
		weight += node.GetValue();
	}
		
	return toIntArray(indices);
}



}
